package com.howtoplayalgorithm.dynamicprogramming;

/**
 * 最长上升子序列
 */
public class Lus {

    static int[] cache;

    public static int longestUpSubSeqBootWWRR(int pos,int[] input){

        long before = System.nanoTime();

        int res = 0;
        for(int i = 1;i <= pos;i ++){
            res = Math.max(res,longestUpSubSeqWWRR(i,input));
        }

        long after = System.nanoTime();
        System.out.println(after - before);

        return res;
    }

    private static int longestUpSubSeqWWRR(int pos, int[] input) {

        if(pos <= 1){
            return 1;
        }

        for(int i = 0;i < input.length;i ++){
            cache[i] = 1;
        }

        for(int i = 0;i < pos;i ++){
            for(int j = i + 1;j < input.length;j ++){
                if(input[i] < input[j]){
                    cache[j] = Math.max(cache[j],cache[i] + 1);
                }
            }
        }

        return cache[pos - 1];
    }


    public static int longestUpSubSeqBootRRWW(int pos,int[] input){

        long before = System.nanoTime();

        int res = 0;
        for(int i = 1;i <= pos;i ++){
            res = Math.max(res,longestUpSubSeqRRWW(i,input));
        }

        long after = System.nanoTime();
        System.out.println(after - before);

        return res;





    }

    private static int longestUpSubSeqRRWW(int i, int[] input) {

        return longestUpSubSeqRRWWInner(i,1,input);
    }

    private static int longestUpSubSeqRRWWInner(int target, int now, int[] input) {
        if(now > target){
            return cache[target - 1];
        }
        int res = 0;
        for(int i = 1;i < now;i ++){
            if(input[i - 1] < input[now - 1]){
                res = Math.max(cache[i - 1],res);
            }
        }
        cache[now - 1] = res + 1;
        return longestUpSubSeqRRWWInner(target,now + 1,input);
    }

    //记忆型递归。
    public static int longestUpSubSeq(int pos,int[] input){
        if(pos == 0){
            return 1;
        }
        if(cache[pos - 1] != 0){
            return cache[pos - 1];
        }

        int max = 0;
        for(int i = 1;i <= pos - 1;i ++){
            int tmp;
            if(input[i - 1] < input[pos - 1]) {
                tmp = longestUpSubSeq(i, input);
                max = Math.max(max, tmp);
            }
        }

        if(cache[pos - 1] == 0){
            cache[pos - 1] = max + 1;
        }
        return max + 1;

    }

    public static int longestUpSubSeqBoot(int pos,int[] input){

        long before = System.nanoTime();

        int res = 0;
        for(int i = 1;i <= pos;i ++){
            res = Math.max(res,longestUpSubSeq(i,input));
        }

        long after = System.nanoTime();
        System.out.println(after - before);

        return res;
    }

    public static void main(String[] args){

        int[] input={3,5,1,2,34,1,4,7};

        cache = new int[input.length];

        System.out.println(longestUpSubSeqBoot(8,input));
        System.out.println(longestUpSubSeqBootRRWW(8,input));
        System.out.println(longestUpSubSeqBootWWRR(8,input));
    }


}
